package com.wayne.leetcode.problems;

import com.wayne.leetcode.ListNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution1019 {
  public static int[] nextLargerNodes(ListNode head) {
    List<Integer> ans = new ArrayList<Integer>();
    int size = -1;
    ListNode cur = head;
    Deque<int[]> stack = new ArrayDeque<int[]>();
    while (cur != null) {
      ++size;
      ans.add(0);
      while (!stack.isEmpty() && stack.peek()[0] < cur.val) {
        ans.set(stack.pop()[1], cur.val);
      }
      stack.push(new int[]{cur.val, size});
      cur = cur.next;
    }
    int[] result = new int[ans.size()];
    for (int i=0;i<ans.size();i++) {
      result[i] = ans.get(i);
    }
    return result;
  }

  public static void main(String[] args) {
    ListNode last = new ListNode(5);
    ListNode node2 = new ListNode(2, last);
    ListNode node1 = new ListNode(5);
    ListNode node = new ListNode(1, node1);
    ListNode head = new ListNode(2, node);
    System.out.println(nextLargerNodes(head));
  }
}